/*
 * @lc app=leetcode.cn id=215 lang=javascript
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

// 快速排序
var findKthLargest1 = function(nums, k) {
    const partition = function(arr, i, j) {
        let p = arr[i]
        while (i < j) {
            while(i < j && arr[j] <= p) j--
            arr[i] = arr[j]
            while(i < j && arr[++i] >= p);
            arr[j--] = arr[i]
        }
        arr[i] = p
        return i
    }
    const sort = function(arr, i, j) {
        let mid = partition(arr, i, j)
        sort(arr, i, mid-1)
        sort(arr, mid+1, j)
    }
    sort(nums, 0, nums.length - 1)
    return nums[k-1]
};


// 堆排序
var findKthLargest2 = function(nums, k) {
    let heap = new Array(nums.length)
    let count = 0
    const swim = function() {
        let cur = count
        // let par = Math.floor(cur / 2)
        let par = cur >> 1
        while (par > 0 && heap[par-1] < heap[cur-1]) {
            let tmp = heap[cur - 1]
            heap[cur - 1] = heap[par - 1]
            heap[par - 1] = tmp
            cur = par
            par = cur >> 1
        }
    }
    const sink = function(i) {
        let cur = i
        let left = 2*cur + 1, right = left + 1
        if (left < count && heap[left] > heap[cur]) {
            cur = left
        }
        if (right < count && heap[right] > heap[cur]) {
            cur = right
        }
        if (cur != i) {
            let tmp = heap[cur]
            heap[cur] = heap[i]
            heap[i] = tmp
            sink(cur)
        }
    }
    const push = function(n) {
        if (count == 0) {
            heap[0] = n
            count++
        } else {
            heap[count++] = n
            swim() // 上浮
        }
    }
    const pop = function() {
        let ans = heap[0]
        heap[0] = heap[--count]
        sink(0) // 下沉
        return ans
    }
    for (let n of nums) push(n)
    let i = 1
    while ((i++) < k) pop()
    let ans = pop()
    return ans
};

// @lc code=end

// findKthLargest([7,6,5,4,3,2,1], 5)